partiels/091105/partiel_Mathsdis_S1_Novembre 09.tex

   1 \documentclass[12pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  10 \usepackage[dvips]{graphics}
  11 \usepackage{epsfig}
  12 \usepackage{calc}
  13 \usepackage{tabls}
  14 \usepackage{slashbox}
  15 \usepackage{times}
  16 \usepackage{tabularx}
  17 \usepackage{textcomp}
  18 \usepackage{pst-all}
  19 \usepackage[a4paper]{geometry}
  20
  21 \input{symboles.sty}
  22 \geometry{hmargin=1cm, vmargin=1.5cm}
  23
  24 \title{
  25 Département d'informatique. \\
  26 Partiel de mathématiques discrètes.\\
  27 Semestre 1 (Novembre 09).\\
  28 }
  29
  30 \date{}
  31
  32 \begin{document}
  33 \maketitle
  34
  35 \noindent Seule une fiche manuscrite de format A5 est autorisée.
  36
  37 \noindent\begin{tabular}{ll}
  38 Nom: &.............................. \\
  39 Prénom: &..............................
  40 \end{tabular}
  41
  42
  43 \section{QCM}
  44
  45 Cette partie contient 47 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).\\
  46
  47 Q. 1. Le nombre $\pi$ est rationnel.
  48 L'assertion proposée est vraie ou fausse ?\\
  49
  50 Q. 2. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. On a $a \in A$. L'assertion proposée est vraie ou fausse ?\\
  51
  52 Q. 3. L'intersection entre deux ensembles est l'ensemble des éléments appartenant aux deux ensembles.
  53 L'assertion proposée est vraie ou fausse ?\\
  54
  55 Q. 4. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. On a $\{d,e,f\} \in A$. L'assertion proposée est vraie ou fausse ?\\
  56
  57 Q. 5. L'intersection de deux ensembles est l'ensemble des éléments appartenant à au moins un des deux ensembles.
  58 L'assertion proposée est vraie ou fausse ?\\
  59
  60 Q. 6. Le complémentaire de l'ensemble des entiers positifs ou nuls dans $\N$ est égal à l'ensemble des entiers strictement négatifs. L'assertion proposée est vraie ou fausse ?\\
  61
  62 Q. 7.
  63 Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{\begin{array}{l}~\end{array}}$.
  64 Si $t_1 . t_2 = 0$ alors $t_1 = \overline{t_2}$.
  65  L'assertion proposée est vraie ou fausse ?
  66 \\
  67
  68 Q. 8.
  69 Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{\begin{array}{l}~\end{array}}$.
  70 Si $t_1 . t_2 = 0$ alors $t_1$ ou $t_2$ sont nuls.
  71  L'assertion proposée est vraie ou fausse ?
  72 \\
  73
  74 Q. 9. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 8 éléments.
  75 L'assertion proposée est vraie ou fausse ?\\
  76
  77 Q. 10. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $E$ qui ne sont pas dans $A$.
  78 L'assertion proposée est vraie ou fausse ?\\
  79
  80 Q. 11. Par convention, $\varnothing$ a 0 élément.
  81 L'assertion proposée est vraie ou fausse ?\\
  82
  83 % Q. 12. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\{d,e,f\} \in A$.
  84 % L'assertion proposée est vraie ou fausse ?\\
  85
  86 Q. 12. La réunion de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ ou à $B$.
  87 L'assertion proposée est vraie ou fausse ?\\
  88
  89
  90 Q. 13. Le cardinal d'un ensemble fini est son nombre d'éléments.
  91 L'assertion proposée est vraie ou fausse ?\\
  92
  93 Q. 14. Il existe un unique ensemble vide. L'assertion proposée est vraie ou fausse ?\\
  94
  95 Q. 15.
  96 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
  97 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
  98 L'égalité $\overline{a}.b.\overline{c}.\overline{d} = 1$ est établie si et seulement si $a+\overline{b} + c+ d =0$. L'assertion proposée est vraie ou fausse ?\\
  99
 100 Q. 16. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 3 éléments.
 101 L'assertion proposée est vraie ou fausse ?\\
 102
 103 Q. 17. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $E$ qui ne sont pas dans $A$. L'assertion proposée est vraie ou fausse ?\\
 104
 105 Q. 18. Le complémentaire des entiers pairs dans $\N$ est égal à l'ensemble des entiers impairs. L'assertion proposée est vraie ou fausse ?\\
 106
 107 Q. 19. Le nombre $\pi$ est irrationnel.
 108 L'assertion proposée est vraie ou fausse ?\\
 109
 110 Q. 20. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $ \{c \} \subset A$.
 111 L'assertion proposée est vraie ou fausse ?\\
 112
 113 Q. 21.
 114 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
 115 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
 116 L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $a.b$ vaut 0. L'assertion proposée est vraie ou fausse ?\\
 117
 118 Q. 22. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 4 éléments. L'assertion proposée est vraie ou fausse ?\\
 119
 120 Q. 23. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $A$ qui ne sont pas dans $E$. L'assertion proposée est vraie ou fausse ?\\
 121
 122 Q. 24. $\N$ est un ensemble infini. L'assertion proposée est vraie ou fausse ?\\
 123
 124 Q. 25. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. On a $\emptyset \subset A$. L'assertion proposée est vraie ou fausse ?\\
 125
 126 Q. 26. $\sin(1)$ est irrationnel. L'assertion proposée est vraie ou fausse ?\\
 127
 128 Q. 27. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. On a $\emptyset \in A$.
 129 L'assertion proposée est vraie ou fausse ?\\
 130
 131 Q. 28. $\Z$ est un ensemble infini.
 132 L'assertion proposée est vraie ou fausse ?\\
 133
 134 Q. 29.
 135 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
 136 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
 137 L'expression $a+ \overline{b} + \overline{a}.b + \overline{c}$ est égale à $\overline{c} + 1$. L'assertion proposée est vraie ou fausse ?\\
 138
 139
 140 %Q. 30. $\Z$ est un ensemble infini. L'assertion proposée est vraie ou fausse ?\\
 141
 142 Q. 30. La réunion de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ et à $B$.
 143 L'assertion proposée est vraie ou fausse ?\\
 144
 145
 146 Q. 31. $A \cup B$ est la réunion de $A$ et de $B$.
 147 L'assertion proposée est vraie ou fausse ?\\
 148
 149 Q. 32.
 150 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
 151 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
 152 L'égalité $a+\overline{b}+\overline{c}+\overline{d}=0$ est établie si et seulement si $a$ est la seule variable valant 0. L'assertion  proposée est vraie ou fausse ?\\
 153
 154 % Q. 33. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $A$ qui ne sont pas dans $E$.
 155 % L'assertion proposée est vraie ou fausse ?\\
 156
 157
 158 Q. 33. $A \cup B$ est l'intersection de $A$ et de $B$.
 159 L'assertion proposée est vraie ou fausse ?\\
 160
 161
 162 Q. 34. $A \cap B$ est la réunion de $A$ et de $B$. L'assertion proposée est vraie ou fausse ?\\
 163
 164 Q. 35. $e$ est irrationnel.
 165 L'assertion proposée est vraie ou fausse ?\\
 166
 167 Q. 36.
 168 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
 169 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
 170 L'expression  $\overline{a}.b + a.\overline{b}$ est vraie quand $a$ et $b$ sont différents. L'assertion proposée est vraie ou fausse ?\\
 171
 172 Q. 37. La réunion entre deux ensembles est l'ensemble des éléments appartenant aux deux ensembles.
 173 L'assertion proposée est vraie ou fausse ?\\
 174
 175 % Q. 38. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\emptyset \in A$. L'assertion proposée est vraie ou fausse ?\\
 176
 177 Q. 38.
 178 Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression
 179 $E=\overline{a}.b + a.c + \overline{b}.c + \overline{c}$. La version la plus réduite de $E$ est 0.
 180  L'assertion proposée est vraie ou fausse ?
 181 \\
 182
 183
 184 Q. 39.
 185 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
 186 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
 187 L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $c.d$ vaut 1. L'assertion proposée est vraie ou fausse ?\\
 188
 189 %Q. 40. $A \cap B$ est la réunion de $A$ et de $B$.
 190 %L'assertion proposée est vraie ou fausse ?\\
 191
 192 Q. 40. $\sin(1)$ est rationnel.
 193 L'assertion proposée est vraie ou fausse ?\\
 194
 195
 196 Q. 41. L'intersection de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ ou à $B$.
 197 L'assertion proposée est vraie ou fausse ?\\
 198
 199 %Q. 42. Le nombre $\pi$ est irrationnel. L'assertion proposée est vraie ou fausse ?\\
 200
 201 Q. 42. $A \cap B$ est l'intersection de $A$ et $B$.
 202 L'assertion proposée est vraie ou fausse ?\\
 203
 204
 205 % Q. 43. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 3 éléments. L'assertion proposée est vraie ou fausse ?\\
 206
 207 Q. 43. Le complémentaire de l'ensemble des entiers positifs ou nuls dans $\N$ est égal à l'ensemble des entiers strictement négatifs.
 208 L'assertion proposée est vraie ou fausse ?\\
 209
 210 Q. 44.
 211 Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression
 212 $E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est 1.
 213  L'assertion proposée est vraie ou fausse ?
 214 \\
 215
 216 Q. 45.
 217 Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression
 218 $E=\overline{a}.b + a.c + \overline{b}.c + \overline{c}$. La version la plus réduite de $E$ est 1.
 219  L'assertion proposée est vraie ou fausse ?
 220 \\
 221
 222 Q. 46. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. On a $\{\{a,b\}\} \subset A$.
 223 L'assertion proposée est vraie ou fausse ?\\
 224
 225 %Q. 47. $\sin(1)$ est rationnel. L'assertion proposée est vraie ou fausse ?\\
 226
 227 Q. 47. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. L'ensemble $P(A)$ contient 64 éléments.
 228 L'assertion proposée est vraie ou fausse ?\\
 229
 230
 231
 232
 233
 234
 235 % Q. 54. $A \cup B$ est la réunion de $A$ et de $B$. L'assertion proposée est vraie ou fausse ?\\
 236
 237 % Q. 55.
 238 % On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
 239 % le . est le symbole du ET logique.
 240 % L'égalité $a+\overline{b}+\overline{c}+\overline{d}=0$ est établie si et seulement si $a$ est la seule variable valant 0. L'assertion  proposée est vraie ou fausse ?\\
 241
 242 % Q. 56. $A \cap B$ est l'intersection de $A$ et $B$. L'assertion proposée est vraie ou fausse ?\\
 243
 244
 245
 246 % Q. 59. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $a \in A$.
 247 % L'assertion proposée est vraie ou fausse ?\\
 248
 249
 250
 251 \begin{huge}
 252 \begin{center}
 253 \begin{tabular}{|l|c|c||l|c|c||l|c|c|}
 254 \hline
 255 Numéro & V & F & Numéro & V & F & Numéro & V & F \\
 256 \hline
 257 Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\
 258 \hline
 259 Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\
 260 \hline
 261 Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\
 262 \hline
 263 Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\
 264 \hline
 265 Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\
 266 \hline
 267 Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\
 268 \hline
 269 Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\
 270 \hline
 271 Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\
 272 \hline
 273 Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\
 274 \hline
 275 Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\
 276 \hline
 277 Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\
 278 \hline
 279 Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\
 280 \hline
 281 Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\
 282 \hline
 283 Q. 40 & &  & Q. 41 & &  & Q. 42 & &  \\
 284 \hline
 285 Q. 43 & &  & Q. 44 & &  & Q. 45 & &  \\
 286 \hline
 287 Q. 46 & &  & Q. 47 & &  &  & &  \\
 288 \hline
 289 \end{tabular}
 290 \end{center}
 291 \end{huge}
 292
 293
 294
 295
 296 \newpage
 297
 298 \section{Problèmes}
 299
 300
 301
 302
 303
 304
 305 \subsection{Théorie des ensembles}
 306 Rappel: pour deux ensembles $A$ et $B$, on appelle \emph{différence symétrique}, noté $A\Delta B$, l'ensemble défini par
 307 \[
 308 A \Delta B = (A \cup B) \setminus (A \cap B)
 309 \]
 310 c'est-à-dire que $A \Delta B$ est constitué des éléments qui appartiennent soit à $A$, soit à $B$, mais pas aux deux.
 311 Soit $A$, $B$ et $C$ trois ensembles.
 312
 313 \begin{enumerate}
 314 \item Montrer que l'opérateur est commutatif.
 315 \item Montrer que l'opérateur possède un élément neutre que l'on explicitera.
 316 \item Montrer que si $A \Delta B = A \Delta C$ alors $B = C$.
 317 \end{enumerate}
 318
 319 \subsection{Algèbre de Boole 1}
 320
 321 A l'aide des  méthodes de votre choix (Karnaugh ou consensus),
 322 réécrire les expressions suivantes
 323 en une somme qui contient le moins de monômes.
 324 \begin{enumerate}
 325 \item $A =\overline{c}\overline{d}b + cab + \overline{c}dab + c\overline{d}\overline{a}b + ca\overline{b}$. % ac + ab + b\overline{d}
 326
 327 \item $B =
 328   \overline{a}b\overline{c}\overline{d}+
 329   ab\overline{c} +
 330   a\overline{b}\overline{c}d +
 331   acd +
 332   abc\overline{d} +
 333   \overline{a}\overline{b}d$
 334 % \overline{a}b\overline{c}\overline{d} + ab + \overline{b}d
 335 \end{enumerate}
 336
 337
 338 \subsection{Algèbre de Boole 2}
 339 On considère le jeu avec une équipe de quatre candidats dont un chef d'équipe.
 340 Chaque candidat dispose d'un
 341 boîtier lui permettant de donner un vote de type oui/non.
 342 Un affichage central présente l'avis de la majorité des candidats.
 343 Lorsqu'il y a le même nombre de votes \og oui\fg{} que de votes \og non\fg{}
 344 le vote du chef d'équipe est
 345 prépondérant.
 346 \begin{enumerate}
 347 \item Construire la table de vérité  du système central d'affichage;
 348 \item Exprimez l'affichage centrale en FCD;
 349 \item Formez une expression booléenne minimale de l'affichage.
 350 \end{enumerate}
 351 \end{document}